package Offer2018;

/**
 * 斐波那契数列
 * Created by 雷文康 on 2018/3/3.
 */
public class Test09 {
    public static void main(String[] args) {
        System.out.println(fibonacci1(10));
        System.out.println(fibonacci2(10));
    }

    public static int fibonacci1(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacci1(n - 2) + fibonacci1(n - 1);
    }

    public static long fibonacci2(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        long first = 0;
        long second = 1;
        long result = 0;
        for (long i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }
}
